package com.lc.boxuegu.M_kthSmallest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author zhaiyj
 * @date 2025/6/16 20:30
 */
public class Solution {


    private int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        return dfs(root);
    }

    private int dfs(TreeNode node){
        if(node == null){
            return -1;
        }
        int leftRes = dfs(node.left);
        if(leftRes != -1){
            return leftRes;
        }
        if(--k == 0){
            return node.val;
        }
        return dfs(node.right);
    }

//    private int ans;
//    private int k;
//
//    public int kthSmallest(TreeNode root, int k) {
//        this.k = k;
//        dfs(root);
//        return ans;
//    }
//
//    private void dfs(TreeNode node){
//        if(node == null || k==0){
//            return;
//        }
//
//        dfs(node.left);
//        if(--k == 0){
//            ans = node.val;
//        }
//        dfs(node.right);
//    }



    public int kthSmallest1(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        st.add(root);
        while (!st.isEmpty()) {
            TreeNode pop = st.pop();
            list.add(pop.val);
            if (pop.left != null) {
                st.add(pop.left);
            }
            if (pop.right != null) {
                st.add(pop.right);
            }
        }

        list.sort(Integer::compareTo);
        return list.get(k - 1);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
